In progressive transmission, partial image information is transmitted in a number of successive stages, and at each stage, an approximation to the original image is reconstructed at the receiver. These reconstructed images improve in quality as additional information is transmitted. Progressive transmission is motivated by the need to transmit images over low-bandwidth channels (relative to the amount of data), e.g., telephone lines, particularly in those cases where quick recognition is important or total transmission time may be limited.
One approach to progressive transmission is to successively transmit the bit planes of a continuous-tone image. Bit planes are binary images that are formed by selecting a single bit from the same position in the binary representation of each pixel. A k-bit image with dimensions N.times.N can thus be decomposed into k binary images, each with dimensions N.times.N. An example of bit planes for an 8-bit image is shown in FIG. 1, where the image labeled 0 is the least significant bit (LSB) plane and the image labeled 7 is the most significant bit (MSB) plane. It can be seen that the most significant bit plane contains major structural information and provides a reasonable approximation to the original image. As a result, progressive transmission usually begins by transmitting the MSB plane first and proceeds through the other bit planes in order. At each stage in the reconstruction, one or more bit planes may be transmitted. Upon receiving the LSB plane, a lossless reconstruction of the image can be obtained. To make the transmission scheme more efficient, coding techniques can be applied to the bit planes; this aspect of bit planes is not necessary (nor detrimental) to the invention disclosed herein.
In progressively reconstructing an image using the bit planes, output levels must be specified at each stage in order to map the received data to an output device. For example, if one bit plane (the MSB plane) is received, two output levels are required, which might be 0 and 255 for an 8-bit output device. If two bit planes are received, four output levels are required, e.g., (0, 85 ,170, and 255) for an 8-bit device, and so on as more bit planes are received. There are a number of ways that these output values can be assigned. A simple approach is to assume the output buffers are initially filled with all 0's or all 1's. As bits are received, they are placed in the appropriate positions in the buffers. For example, if the buffers are initially filled with all 0's, the two possible output values after the MSB plane is received are `00000000` and `10000000` (0 and 128) for an 8-bit display. After two bit planes are received, the four possible output values are `00000000`, `01000000`, `10000000`, and `11000000` (0, 64, 128, and 192). With this approach, the images start out dark (assuming 0 represents black) and become lighter as more levels are added. If the output buffers are initially filled with all 1's, then the image starts out light and becomes darker, e.g., the first two output levels are `01111111` and `11111111` (127 and 255).
A more sophisticated approach is to use look-up tables so that the output levels at each stage can be varied at will. A block diagram representing a prior-art technique is shown in FIG. 2, wherein 0 through k-1 bit planes are transmitted successively, starting with the bits of bit plane k-1 to the input of a bit combination logic block 12. Each bit in a bit plane corresponds to a single pixel of the original image, and the combination of one or more of the bits, corresponding to a pixel can be used to form a digital representation of the pixel for later reproduction. To this end, block 12 also receives as an input from a previous bits recovery logic block 20, the bits from previously received bit planes and appends the most recently received bit to the previously received bits of the corresponding pixel and provides this sequence of bits at its output. The previous bits recovery logic block 20 takes as an input from an n-bit output frame buffer 18, the previously reconstructed output value for the corresponding pixel and outputs the received bit sequence that produced this reconstructed value. A means for performing the recovery of previously received bits from the reconstructed output value is demonstrated in the section on Description of the Preferred Embodiments. The appended sequence of bits from block 12 is directed to the input of a look-up address generation logic block 14. The bit sequence is used to generate a unique address to be used as an entry into a look-up table 16. A block diagram illustrating a prior art method for generating the address is shown in FIG. 3, where the received bits are placed in an address buffer 32, and then additional bits are appended using a logic block 34 to complete the address. The appended bits consist of a variable number of "don't care" bits, i.e., either 0 or 1, plus a fixed number of steering bits to direct the received bit sequence to the appropriate portion of the look-up table for the total number of bits received. For an output device supporting n bits, if we have received a total of m bits for each pixel, then n-m "don't care" bits are appended and the number of steering bits is ceil[log.sub.2 n], where ceil[x] indicates the smallest integer larger than x. An example is shown in Table 1 for the first three received bits of an image with an 8 bit output device, where an "x" in the look-up table address represents a "don't care" bit. For this example, the received bits are appended with enough "don't care" bits to make a total of eight bits, and then three steering bits are added to direct the result to the appropriate section of the look-up table. Returning to FIG. 2, the look-up table address is applied to an output value look-up table 16 to access an n-bit output value that is placed in the output frame buffer 18 as a cumulative representation of the received bits for the corresponding pixel. An n-bit display 10 is coupled to the output buffer to provide a visual image of the progression of the reconstruction.
TABLE 1 ______________________________________ Example of look-up table addresses. Received Look-up Table Bits Address ______________________________________ 0 0xxxxxxx000 1 1xxxxxxx000 00 00xxxxxx001 01 01xxxxxx001 10 10xxxxxx001 11 11xxxxxx001 000 000xxxxx010 001 001xxxxx010 010 010xxxxx010 011 011xxxxx010 100 100xxxxx010 101 101xxxxx010 110 110xxxxx010 111 111xxxxx010 ______________________________________
Using this look-up table approach, an important question is what output levels should be used to maximize image recognizability at the early stages of the progression. The answer to this is not clear, but two approaches suggest themselves. One is to use the mean values of the possible ranges represented by the transmitted bits. This is the optimal mapping in a mean-squared error (MSE) sense. For example, after the MSB plane is received, the two possible ranges for an 8-bit display are 0 to 127 and 128 to 255, and the corresponding mean values are 63 and 191. After two bits are received, the mean values for the four possible ranges are (31, 95, 159, 223). Note that this optimal MSE approach does not take advantage of the full dynamic range of the output display, which suggests another method where the possible output values are equally spaced across the full range. For this method, the output values for an 8-bit display would be (0,255) after the MSB plane is received, (0, 85, 170, 255) after two bits, and so on.
Despite offering great flexibility in the mapping of bit planes to output values, the look-up table method has a potential disadvantage, namely, output devices with a large dynamic range, e.g., 10 or 12 bits, require fairly large look-up tables. This is because the address used as an entry into the look-up table consists of the received bits, plus the steering bits needed to direct the received bits to the appropriate portion of the table for the total number of bits received. For example, a 12-bit output device must have a table that can support a maximum of 12 received bits plus 4 steering bits, for a total size of 2.sup.16 entries. In addition, the look-up table method requires at least some additional circuitry to generate the address of the memory location storing the appropriate output value. Two publications of interest for their teachings in this area are:
1. K.-H. Tzou, "Progressive image transmission: a review and comparison of techniques," Opt. Eng., 26(7), pp. 581-589 (1987); and PA1 2. M. Rabbani and P. W. Jones, Digital Image Compression Techniques, SPIE Tutorial Series, Vol. TT7, SPIE Press, Bellingham, Wash., pp. 49-57 (1991). PA1 a) receiving one or more bits of the k-bit representation to produce a sequence of m bits, where m represents the total number of received bits; PA1 b) forming an n-bit output value by combining an n-m bit sequence with the sequence of m bits of step a); PA1 c) buffering the formed n-bit output value; PA1 d) recovering the previously received m bits from the buffered n-bit output value; PA1 e) receiving one or more of the remaining bits of the k-bit representation; PA1 f) combining the received bits of step e) with the recovered m bits of step d) to form a new m-bit sequence, where m is incremented to represent the new total nurser of received bits; PA1 g) forming a new n-bit output value by combining an n-m bit sequence with the m-bit sequence of step f); PA1 h) buffering the formed n-bit output value of step g); and PA1 i) repeating steps d) through h) to a desired received bit depth.